#include<vector>
using namespace std;
class Solution {
int N=1000000007;
public:
    int waysToStep(int n) {
        vector<int>dp(n+1,0);
        if(n==1||n==2)return n;
        dp[0]=0,dp[1]=1,dp[2]=2,dp[3]=4;

        //o(n)时间复杂度 o(n)时间复杂度
        for(int i=4;i<=n;i++)
        {
            dp[i]=((dp[i-1]%N+dp[i-2])%N+dp[i-3]%N)%N;
        }
        return dp[n];
        
    }
};